package com.mashibing.class16;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

// lintcode 127 : 拓扑排序
// OJ链接：https://www.lintcode.com/problem/topological-sorting

/**
 * 给定一个有向图，图节点的拓扑排序定义如下:
 * 对于图中的每一条有向边 A -> B , 在拓扑排序中A一定在B之前.
 * 拓扑排序中的第一个节点可以是图中的任何一个没有其他节点指向它的节点.
 * 针对给定的有向图找到任意一种拓扑排序的顺序.
 */
public class Code03_TopologicalOrderDFS1 {
    // 不要提交这个类
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }

    // 提交下面的
    public static class Record {
        public DirectedGraphNode node; // 当前节点
        public int deep; // 节点的深度

        public Record(DirectedGraphNode n, int o) {
            node = n;
            deep = o;
        }
    }

    public static class MyComparator implements Comparator<Record> {

        @Override
        public int compare(Record o1, Record o2) {
            return o2.deep - o1.deep;// 谁的深度大 谁就排在前面.
        }
    }

    // 拓扑排序的总入口, 给定指定点的集合, 将指定点进行排序.
    public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        HashMap<DirectedGraphNode, Record> order = new HashMap<DirectedGraphNode, Record>();
        for (DirectedGraphNode cur : graph) {
            f(cur, order);
        }
        // 取出order集合中的所有元素 缓存至 recordArr 中.
        ArrayList<Record> recordArr = new ArrayList<Record>();
        for (Record r : order.values()) {
            recordArr.add(r);
        }
        //  recordArr 的元素进行排序。
        recordArr.sort(new MyComparator());
        // 新建一块新缓存ans， 将recordArr中的 中的每个元素 Record中的node节点 一一插入ans缓存.
        ArrayList<DirectedGraphNode> ans = new ArrayList<DirectedGraphNode>();

        for (Record r : recordArr) {
            ans.add(r.node);
        }
        return ans;
    }

    public static Record f(DirectedGraphNode cur, HashMap<DirectedGraphNode, Record> order) {
        if (order.containsKey(cur)) {
            return order.get(cur);
        }
        int follow = 0;
        // 取出当前节点cur的所有邻居节点的最大深度
        for (DirectedGraphNode next : cur.neighbors) {
            follow = Math.max(follow, f(next, order).deep);
        }
        // 当前节点的深度为 follow+1 构建一个 Record 记录.
        Record ans = new Record(cur, follow + 1);
        order.put(cur, ans);
        return ans;
    }
}
